import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/23 22:20
 * @description 01字典树，将数的二进制看成一个字符串，可以建立字符集为{0，1}的字典树。
 * 作用：
 *      维护异或极值
 *      维护异或和
 *          插入|删除
 *          全局 + 1
 *      01trie合并
 */
public class Trie01 {
    /**
     * 二进制最高位 int型是30，long型是62
     */
    static int highBit = 30;

    /**
     * children[0] 当前位 0
     * children[1] 当前位 1
     */
    Trie01[] children = new Trie01[2];

    /**
     * 如果使用，可以记录当前节点下的子串数量
     */
    int cnt = 0;

    /**
     * 字典树中插入值val
     * @param val val
     */
    public void insert(int val) {
        Trie01 node = this;
        for(int i = highBit; i >= 0; i--) {
            // 右移i位，或者 bit = (1 >> i ) & val
            int bit = (val >> i) & 1;

            if (node.children[bit] == null) {
                node.children[bit] = new Trie01();
            }
            node = node.children[bit];
            // node.cnt++;
        }
    }

    /**
     * 获取val和当前字典树中一个数的最大异或和
     * @param val val
     * @return max(num[j] ^ val)
     */
    public int getMaxXor(int val) {
        int ans = 0;
        Trie01 node = this;
        for(int i = highBit; i >= 0; i--) {
            int bit = (val >> i) & 1;
            if (node.children[bit ^ 1] != null) {
                // 说明最终结果中，当前位能贪心到1
                ans |= (1 << i);
                bit ^= 1;
            }
            // 取了相异的一个节点，转移
            node = node.children[bit];
        }
        return ans;
    }

}

